package mianjing;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;
import javatest.ClassLoaderTest;

public class TreeIncrusive {

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 5, 8, 9, 3, 6, 10, 11, 12};
        int[] in = {4, 7, 2, 8, 5, 9, 1, 3, 10, 12, 11, 6};
        TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
        TreeIncrusive object = new TreeIncrusive();
        System.out.println(object.getDepth(root));
    }

    // 树的中序遍历
    void testInOrder(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = node;
        while (!stack.empty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode tmp = stack.pop();
            System.out.println(tmp.val);
            cur = tmp.right;
        }
    }

    // 获取树的深度，非递归
    int getDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        Stack<TreeNode> stack = new Stack<>();
        HashMap<TreeNode, Integer> map = new HashMap<>();
        stack.push(node);
        map.put(node, 1);
        int res = 0;
        while (!stack.empty()) {
            TreeNode tmp = stack.pop();
            int curDepth = map.getOrDefault(tmp, 0);
            int leftDepth = curDepth;
            int rightDepth = curDepth;
            System.out.println(tmp.val);
            if (tmp.left != null) {
                stack.push(tmp.left);
                leftDepth = curDepth + 1;
                map.put(tmp.left, leftDepth);
            }
            if (tmp.right != null) {
                stack.push(tmp.right);
                rightDepth = curDepth + 1;
                map.put(tmp.right, rightDepth);
            }
            res = Math.max(res, Math.max(leftDepth, rightDepth));
        }
        for (Map.Entry<TreeNode, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey().val + " depth: " + entry.getValue());
        }
        return res;
    }
}
